"""
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true
示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/introduction-to-data-structure-binary-search-tree/xpkc6i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def inorderTraversal(node: TreeNode):
            r = []
            if node is not None:
                r.extend(inorderTraversal(node.left))
                r.extend([node.val])
                r.extend(inorderTraversal(node.right))
            return r
        a = inorderTraversal(root)
        return all(a[i] < a[i+1] for i in range(len(a) - 1))

    def is_valid_bst(self, root: TreeNode) -> bool:
        values = lambda x: [] if not x else values(x.left) + [x.val] + values(x.right)
        a = values(root)
        return all(a[i] < a[i + 1] for i in range(len(a) - 1))


if __name__ == '__main__':
    tree = TreeNode(2)
    tree.left = TreeNode(1)
    tree.right = TreeNode(3)
    # tree.right.left = TreeNode(6)
    # tree.right.right = TreeNode(20)
    s = Solution()
    print(s.isValidBST(tree))
    print(s.is_valid_bst(tree))
